package com.atguigu.practice;

public class MorrisPre {
    public static void morrisPre(Node head){
        if(head==null){
            return;
        }
        Node cur=head;
        Node mostRight=null;
        while(cur!=null){
            mostRight=cur.left; //mostRight是cur左孩子
            if(mostRight!=null) {//有左子树
                while(mostRight.right!=null && mostRight.right!=cur){
                    mostRight=mostRight.right;
                }
                //mostRight变为cur左子树上最右节点
                if(mostRight.right==null){ //这是第一次来到cur
                    System.out.println(cur.val);
                    mostRight.right=cur;
                    cur=cur.left;
                    continue;
                }else{
                    mostRight.right=null;
                }
            }else{ //没有左子树的情况
                System.out.println(cur.val);
            }
            cur=cur.right;
        }
    }
}
